-----------------------------------------------------------------------------
--
-- Module      :  SP
-- Copyright   :
-- License     :  AllRightsReserved
--
-- Maintainer  :
-- Stability   :
-- Portability :
--
-- |
--
-----------------------------------------------------------------------------

module SP where

import Fixpoint as F
import Trie as T
import Data.Set as S
import Dist
import Data.Maybe
import POrd

type Vertex = String
type Graph = S.Set(Vertex, Vertex)


-- Rekursiv aufgerufen wird indirectPath
-- der Algorithmus terminiert, da der Fixpunktalgorithmus abbricht, wenn es keine Aenderungen mehr gibt
-- es gibt nur Aenderungen, wenn eine Distanz kuerzer ist als die bisherige (in findMinDist)
-- die Entfernung zu anderen Knoten kann nicht kleiner als 1 werden
-- daher kann es irgendwann keine Aenderungen mehr geben
-- dann ist das Minimum erreicht und der Algorithmus bricht ab  
sp :: Graph -> Vertex -> Trie Dist
sp g v         = condFixpoint (indirectPath g v) (startTrie v g)

startTrie v g =
    let infinityTrie = S.fold (\ (v1, v2) trie -> T.insert v2 Infinity (T.insert v1 Infinity trie)) T.empty g
    in
        T.insert v (Value 0) infinityTrie

indirectPath :: Graph -> Vertex -> Trie Dist -> Trie Dist
indirectPath g v sp =
    T.foldTK (\ key _ trie -> T.insert key (dist key trie g) trie) sp sp

dist :: Vertex -> Trie Dist -> Graph -> Dist
dist v sp g =   S.fold (findMinDist v sp) (fromJust(T.lkup v sp))  g
                
findMinDist :: Vertex -> Trie Dist -> (Vertex, Vertex) -> Dist -> Dist
findMinDist v sp (v1, v2) currentMin =
    if v == v2 then
        let 
                predDist = fromJust(T.lkup v1 sp)
        in
                if((predDist `add` 1) `ple` currentMin) then
                        predDist `add` 1
                else
                        currentMin
    else
        currentMin

testGraph = S.fromList [
        ("a","b"),
        ("a","d"),
        ("d","e"),
        ("e","b"),
        ("b","c"),
        ("c","b"),
        ("e","c")
    ]



